package com.zwh.se.collection.list;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author yexi
 * <p>
 * LinkedList: List 接口的链接列表(链表)实现。
 * 特点:
 * 1、 双向链表,特别适合添加、删除的场景
 * 2、 允许包括 null 在内的所有元素。
 * 3、 除了实现 List 接口外，LinkedList同时还实现了 Deque extends Queue 接口,因此也可以用作队列、双向队列、堆栈来使用
 * (有趣的是,本质上它们的操作调用的都是同一个方法,只是名字不一样)
 * 4、 此实现不是同步的
 * TIPS:在本demo中为了突出list的特点,并未指定泛型,在实际使用时,请务必指定泛型再加以使用
 * <p>
 * 总结: 1>使用 remove/element/get/get(index) 系列方法会抛出 NoSuchElementException 异常
 * 2>使用 offer(因为是新增)/poll/peek 系列方法即便找不到也只是返回特殊值 null
 *
 * TIPS: LinkedList 本质上就是通过跳转结构(具体实现为双向链表)来实现的线性表
 */
@SuppressWarnings({"rawtypes", "unchecked"})
public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        System.out.println("--------------------[1]新增操作--------------------");
        //boolean offer(E e)  等同于 boolean add(E e)
        //boolean add(E e);将指定的元素追加到 list 的末尾,内部方法实现等同于调用addLast(E e)
        //boolean offerLast(E e) ,内部方法实现等同于调用addLast(E e)
        list.add("B");
        //void push(E e) 等同于 addFirst(E e)
        //void addFirst(E e) 将指定元素插入 list 的开头。
        //boolean offerFirst(E e) ,内部方法实现等同于调用addFirst(E e)
        list.push("A");
        //void addLast(E e) 将指定元素添加到 list 的结尾。
        list.addLast("C");

        //boolean addAll(Collection<? extends E> c)
        //重载:boolean addAll(int index, Collection<? extends E> c);
        // 添加指定 collection 中的所有元素到 list 的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
        // 使用重载方法添加索引时,从指定位置开始插入。
        list.addAll(list.size(), Arrays.asList("D", "E"));
        System.out.println(list);//[A, B, C, D, E]
        System.out.println("--------------------------------------------");

        System.out.println("--------------------[2]查询操作--------------------");
        //E element()  等同于 E getFirst()
        //E getFirst() 返回此列表的第一个元素
        //E peekFirst() 获取但不移除此列表的头(第一个元素),内部实现类似于getFirst()
        //E peek()     跟 peekFirst() 一模一样
        System.out.println(list.element());//A
        //E getLast() 返回此列表的最后一个元素。
        //E peekFirst() 获取但不移除此列表的最后一个元素。,内部实现类似于getLast()
        System.out.println(list.getLast());//E
        //int indexOf(Object o):返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。
        System.out.println(list.indexOf("A"));//0
        //返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回 -1。
        System.out.println(list.lastIndexOf("E"));//4
        System.out.println("--------------------------------------------");

        System.out.println("--------------------[3]修改操作--------------------");
        //E set(int index, E element) 用指定的element替换并返回指定index上的元素
        System.out.println(list.set(0, "a"));//返回值是被替代的元素:A
        System.out.println("--------------------------------------------");

        System.out.println("--------------------[4]移除操作--------------------");
        //E remove() :   未指定元素,则等同于 removeFirst()
        //E removeFirst() 移除并返回此列表的第一个元素。
        System.out.println(list.remove());//a
        //E removeLast()  移除并返回此列表的最后一个元素。
        System.out.println(list.removeLast());//E
        //E poll()  获取并移除此列表的头部元素(第一个元素),若列表为空,则返回null(做了判断)。跟 pollFirst() 一模一样
        //          (同理 poll 系列方法都是列表为空返回null的)
        System.out.println(list.poll());//B
        //E pollLast() 获取并移除此列表的尾部元素(最后一个元素),若列表为空,则返回null。
        System.out.println(list.pollLast());//D
        System.out.println("--------------------------------------------");

        System.out.println("--------------------[5]其它操作--------------------");
        //int size();返回list中的元素数
        System.out.println(list.size());//1
        //LinkedList的toString调用的是AbstractCollection下的toString,这个类会帮你将元素迭代一遍后再输出出来
        System.out.println(list.toString());
        // void clear() 从此列表中移除所有元素。
        list.clear();

        System.out.println("--------------------[6]LinkedList源码解析--------------------");
        /**
         * @see LinkedList#size  集合中元素的数量
         * @see LinkedList#first  链表的首节点
         * @see LinkedList#last  链表的尾节点
         * @see LinkedList.Node LinkedList 的 Node静态内部类
         *
         *         E item; //当前元素
         *         Node<E> next; //指向下一个元素地址
         *         Node<E> prev; //指向上一个元素地址
         *
         *         Node(Node<E> prev, E element, Node<E> next) {
         *             this.item = element;
         *             this.next = next;
         *             this.prev = prev;
         *         }
         *
         */
        list = new LinkedList();
        /**
         * @see LinkedList#add(Object e)  //添加元素操作(插到链表的尾部)
         *         linkLast(e);
         *         return true;
         *
         * @see LinkedList#linkLast(Object e)  //添加时对元素的具体操作
         *         final Node<E> l = last;  //将链表中的last节点给l 如果是第一个元素的话则此时last为null
         *         //将元素封装为一个Node具体的对象：
         *         final Node<E> newNode = new Node<>(l, e, null); //将该元素的上一个节点设为l,元素是e,下一个节点没有所以设为null
         *         //将链表的last节点指向新的创建的对象：
         *         last = newNode;
         *         if (l == null) //如果添加的是第一个节点
         *             first = newNode; //将链表的first节点指向为新节点
         *         else //如果添加的不是第一个节点
         *             l.next = newNode; //将l的下一个指向为新的节点
         *         size++; //集合中元素数量加1操作
         *         modCount++;
         *
         */
        list.add("ele");
        /**
         * @see LinkedList#get(int index)   //通过索引得到元素
         *         checkElementIndex(index); //健壮性考虑,姑且可以不看
         *         return node(index).item;
         *
         * @see LinkedList#node(int index) // 返回指定元素索引处的（非空）节点。
         *         // size >> 1 : 定位到链表的中间位置
         *         //如果index在链表的前半段，那么从前往后找
         *         if (index < (size >> 1)) {
         *             Node<E> x = first;
         *             for (int i = 0; i < index; i++)
         *                 x = x.next;
         *             return x;
         *         }
         *         //如果index在链表的后半段，那么从后往前找
         *         else {
         *             Node<E> x = last;
         *             for (int i = size - 1; i > index; i--)
         *                 x = x.prev;
         *             return x;
         *         }
         */
        System.out.println(list.get(0));

    }
}
